package com.ztom.daily.n2022.m5;

/**
 * 序列化和反序列化二叉搜索树
 * <p>
 * https://leetcode.cn/problems/serialize-and-deserialize-bst/
 *
 * @author ZhangTao
 */
public class Day11Codec {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public class Codec {

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (root == null) {
                return null;
            }
            StringBuilder sb = new StringBuilder();
            preOrder(root, sb);
            return sb.substring(0, sb.length() - 1);
        }

        private void preOrder(TreeNode node, StringBuilder sb) {
            if (node == null) {
                return;
            }
            sb.append(node.val).append(",");
            preOrder(node.left, sb);
            preOrder(node.right, sb);
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data == null || data.length() == 0) {
                return null;
            }
            String[] split = data.split(",");
            return dfs(0, split.length - 1, split);
        }

        private TreeNode dfs(int l, int r, String[] split) {
            if (l > r) {
                return null;
            }
            int rootVal = Integer.parseInt(split[l]);
            TreeNode root = new TreeNode(rootVal);
            // 找到左右子树的分界线  先序: [4, 2, 1, 3, 6, 5, 7]
            int i = l + 1;
            while (i <= r && Integer.parseInt(split[i]) <= rootVal) {
                i++;
            }
            root.left = dfs(l + 1, i - 1, split);
            root.right = dfs(i, r, split);
            return root;
        }
    }
}
